package cn.demoncat.util.lang.entity.data;

import cn.demoncat.util.exception.ParamRuntimeException;

/**
 * 单向有序链表
 * 
 * @author 延晓磊
 *
 * @since 2020年6月27日
 */
public class SingleSortLinkedList<E extends Comparable<E>> extends SingleLinkedList<E>{

	/**
	 * 添加（根据顺序插入）
	 * 
	 * @param e
	 * 
	 * @author 延晓磊
	 * @return 
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public SingleSortLinkedList<E> add(E e) {
		if (first == null) {
			// 首次添加
			first = new LinkedNode<>(e, null);
			last = first;
		} else {
			if (e.compareTo(first.getData()) < 0) {
				// 头部插入
				first = new LinkedNode<>(e, first);
			}else {
				// 中间插入
				LinkedNode<E> prev = first;
				LinkedNode<E> next = first.next;
				while (next != null) {
					if (e.compareTo(next.getData()) < 0) {
						// prev < e < next
						prev.setNext(new LinkedNode<>(e, next));
						break;
					}else {
						// prev < next < e
						prev = next;
						next = prev.next;
					}
				}
				// 末尾插入
				if (next == null) {
					last.setNext(new LinkedNode<>(e, null));
					last = last.getNext();
				}
			}
		}
		// 计数
		size ++;
		return this;
	}

	/**
	 * 添加（根据顺序插入）
	 * 
	 * @param e
	 * 
	 * @author 延晓磊
	 * @return 
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public SingleSortLinkedList<E> first(E e) {
		return add(e);
	}
	
	/**
	 * 插入（根据顺序插入，索引无效）
	 * 
	 * @param index 索引
	 * @param e
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public void insert(int index, E e) {
		add(e);
	}

	/**
	 * 修改
	 * 
	 * @param index 索引
	 * @param e		新数据（须compare相等，否则顺序会乱）
	 * 
	 * @throws RuntimeException 索引越界：index < 0 || index >= size
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月27日
	 */
	@Override
	public E set(int index, E e) {
		// 索引越界
		if (index < 0 || index >= size) {
			throw INDEX_EX;
		}
		// 找到索引位当前节点
		LinkedNode<E> node = first;
		for (int i = 0; i < index; i++) {
			node = node.getNext();
		}
		// 节点原数据
		E old = node.getData();
		if (old.compareTo(e) != 0) {
			throw new ParamRuntimeException("新数据的排序值必须同于原数据");
		}
		// 修改节点数据
		node.setData(e);
		return old;
	}


}
